//
// Created by 86138 on 2025/5/4.
//
#include "LinkList.h"

void InitList(LinkList &L) {
    // 你会发现这和SqList的初始化完全不同，SqList是在栈上自动分配内存的，且通过点运算符访问Elem指针变量，初始化的时候只需手动分配Elem指针指向的内存（堆上）。
    // LinkList L变量是指针，它指向的对象是在堆上手动分配内存的，所以L就是头指针，它指向的地址就是头结点，而头结点的Next指针在初始化的时候指向NULL。
    L = (LinkList) malloc(sizeof(LNode));
    if (!L) exit(OVERFLOW);

    L->Next = NULL;
}

Boolean IsEmpty(LinkList &L) {
    if (!L->Next) return TRUE;
    else return FALSE;
}

void DestroyList(LinkList &L) {
    // 销毁单链表时，头结点和数据结点本质上一样，所以不需要区别对待。所以一共只需要两个指针。
    LNode *p;
    while (L) {
        p = L;
        L = L->Next;
        free(p);
    }
}

void ClearList(LinkList &L) {
    // 清空单链表，需要保留头结点
    LNode *p, *q;
    p = L->Next;
    while (p) {
        q = p->Next;
        free(p);
        p = q;
    }
    L->Next = NULL;
}

int ListLength(LinkList &L) {
    int count = 0;
    LNode * p;
    p = L->Next;
    while (p) {
        count++;
        p = p->Next;
    }
    return count;
}

void DispList(LinkList &L) {
    LNode *p = L->Next;
    while (p) {
        printf("%d ", p->Data);
        p = p->Next;
    }
    printf("\n");
}

Status GetElem(LinkList &L, int i, ElemType &e) {
    LNode *p;
    p = L->Next;
    int j = 1;
    while (p && j < i) {
        p = p->Next;
        j++;
    }

    if (!p || j > i) { // j > i说明i是诸如0, -1等的位置，这样就不用在函数开头判断i < 1了
        printf("要插入的位置i = %d错误\n", i);
        return ERROR;
    }
    e = p->Data;
    return OK;
}

LNode *LocateElem(LinkList &L, ElemType e) {
    LNode *p;
    p = L->Next;
    while (p && p->Data != e) {
        p = p->Next;
    }
    return p; // 如果没找到，返回NULL，所以调用方要做判断
}

int LocateElem2(LinkList &L, ElemType e) {
    LNode *p;
    p = L->Next;
    int j = 1;
    while (p && p->Data != e) {
        p = p->Next;
        j++;
    }
    if (p) return j;
    return -1;
}

/* 在第i个元素之前插入新元素e。注意在第n + 1个元素之前插入也是允许的，即等同于在表尾追加 */
Status ListInsert(LinkList &L, int i, ElemType e) {
    // 只需要两个指针，不需要第三个指针
    LNode *p;
    p = L; // 必须指向头结点，而不是首元结点，否则当链表为空时，当想在第1个元素之前插入，就会失败
    int j = 0;
    while (p && j < i - 1) {
        p = p->Next;
        j++;
    }

    if (!p || j > i - 1) {
        printf("要插入的位置i = %d错误\n", i);
        return ERROR;
    }

    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->Data = e;
    s->Next = p->Next;
    p->Next = s;

    return OK;
}

/* 删除第i个元素。注意不允许删除第n + 1个元素。 */
Status ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p, *q;
    p = L;
    int j = 0;
    while (p->Next && j < i - 1) {
        p = p->Next;
        j++;
    }

    // 不允许删除第n + 1个元素
    if (!(p->Next) || j > i - 1) {
        printf("要删除的位置i = %d错误\n", i);
        return ERROR;
    }
    q = p->Next;
    e = q->Data;
    p->Next = p->Next->Next; // 或者写成p->Next = q->Next;
    free(q);

    return OK;
}

/* 头插法创建链表 */
void CreateList_H(LinkList &L, int n) {
    InitList(L);
    printf("请输入%d个整数\n", n);
    ElemType e;
    LNode *p;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &e);
        p = (LNode *) malloc(sizeof (LNode));
        if (!p) exit(OVERFLOW);
        p->Data = e;
        p->Next = L->Next;
        L->Next = p;
    }
}

/* 尾插法建立链表 */
void CreateList_R(LinkList &L, int n) {
    InitList(L);
    ElemType e;
    LNode *p, *r;
    r = L; // 尾指针r和头指针L都指向头结点
    printf("请输入%d个整数\n", n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &e);
        p = (LNode *) malloc(sizeof (LNode));
        if (!p) exit(OVERFLOW);
        p->Data = e;
        p->Next = NULL;
        r->Next = p;
        r = p;
    }
}
